package com.owulia.leetcode.sort;

import com.alibaba.fastjson.JSONObject;

public class CommonSort {


    public static void bubble(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i++) {
            boolean change = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    change = true;
                }
            }
            if (!change) {
                break;
            }
        }
    }


    public static void insertion(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int value = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (array[j] > value) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = value;
        }

    }


    public static void merge(int[] array) {
        merge(array, 0, array.length - 1);
    }

    private static void merge(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int middle = (start + end) / 2;
        merge(array, start, middle);
        merge(array, middle + 1, end);


        int[] tempArray = new int[end - start + 1];
        int i = start, j = middle + 1, k = 0;
        while (i <= middle && j <= end) {
            if (array[i] <= array[j]) {
                tempArray[k++] = array[i];
                i++;
            } else {
                tempArray[k++] = array[j];
                j++;
            }
        }
        int left = i;
        int right = middle;
        if (j <= end) {
            left = j;
            right = end;
        }

        while (left <= right) {
            tempArray[k++] = array[left++];
        }

        System.arraycopy(tempArray, 0, array, start, end - start + 1);
    }

    public static void quick(int[] array) {
        quick(array, 0, array.length - 1);
    }

    public static void quick(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
        int i = start, j = end, x = array[start];
        while (i < j) {
            // 从右向左找第一个小于x的数
            while (i < j && array[j] >= x)
                j--;
            if (i < j)
                array[i++] = array[j];

            while (i < j && array[i] < x) // 从左向右找第一个大于等于x的数
                i++;
            if (i < j)
                array[j--] = array[i];
        }
        System.out.println(JSONObject.toJSON(array));


        array[i] = x;
        quick(array, start, i - 1); // 递归调用
        quick(array, i + 1, end);
    }


    public static void radixSort(int[] array, int n) {
        int max = 0;
        for (int i = 0; i < n; i++) {
            if (max < array[i]) {
                max = array[i];
            }
        }
        int[] countNum = new int[max + 1];
        for (int i = 0; i < n; i++) {
            countNum[array[i]] = countNum[array[i]] + 1;
        }
        for (int i = 1; i <= max; i++) {
            countNum[i] = countNum[i - 1] + countNum[i];
        }

        int[] tempArray = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            int index = countNum[array[i]] - 1;
            tempArray[index] = array[i];
            countNum[array[i]] = countNum[array[i]] - 1;

        }
        System.arraycopy(tempArray, 0, array, 0, n);
    }


    public static void main(String[] args) {
        int[] array = {3, 2, 3, 3, 1, 2};
        radixSort(array, array.length);
        System.out.println(JSONObject.toJSON(array));
    }


}
